home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / man / oldman3 / N_Tree.3T < prev    next >
Text File  |  1992-06-26  |  8KB  |  228 lines
  1. .TH N_TREE
  2. .SH NAME
  3. N_Tree<Node,Type,nchild>\f1  A parameterized N-ary tree class
  4. .SH SYNOPSIS
  5. #include <cool/N_Tree.h>
  6. .SH DESCRIPTION
  7. The \f3N_Tree<Node,Type,nchild>\f1 class implements n-ary trees, providing the 
  8. organizational structure for a tree (collection) of nodes, but knowing nothing 
  9. about the specific type of node used. \f3N_Tree<Node,Type,nchild>\f1 is parameterized 
  10. over a node type, a data type, and a subtree count, where the node specified 
  11. must have a data member of the same 
  12.  Type 
  13. as the tree class and the subtree 
  14. count indicates the number of possible subtree pointers (children) from any 
  15. given node. Two node classes are provided, but others could also be written. 
  16. The \f3N_Node<Type> \f1class implements static-sized nodes for some distinct number of subtrees, and the \f3D_Node<Type>\f1 class implements dynamic-sized nodes derived from the \f3Vector<Type>\f1 class.
  17. .PP
  18. Since the organization of a tree is important (as with an expression tree),  
  19. the user must supervise the construction of the tree by directing specific node 
  20. and subtree assignments and layout. No attempt is made by the 
  21. \f3N_Tree<Node,Type,nchild>\f1 class to balance or prune the tree.
  22. .PP
  23. The \f3N_Tree<Node,Type,nchild>\f1 class implements the notion of a current position. 
  24. This is useful for iterating through the nodes of a tree. The current position 
  25. is maintained in a data member of type 
  26.  N_Tree_state 
  27. and is set or reset by all 
  28. member functions affecting elements in the class. Member functions are provided 
  29. to reset the current position, move to the next and previous elements, find an 
  30. element, and get the value at the current position. The 
  31.  Iterator< Type > 
  32. class 
  33. provides a mechanism to save and restore the state associated with the current 
  34. position, thus allowing the programmer to use multiple iterators over the same 
  35. instance of a tree.
  36. .PP
  37. Traversal through an n-ary tree using the current position mechanism and the 
  38.  Iterator< Type > 
  39. class can be controlled by setting the traversal mode. An 
  40. enumerated type 
  41.  Traversal_Type 
  42. is defined for the following values:
  43. .PP
  44. .TP .2i
  45. \(bu
  46. PREORDER
  47. .TP
  48. \(bu
  49. PREORDER_REVERSE
  50. .TP
  51. \(bu
  52. INORDER
  53. .TP
  54. \(bu
  55. INORDER_REVERSE
  56. .TP
  57. \(bu
  58. POSTORDER
  59. .TP
  60. \(bu
  61. POSTORDER_REVERSE
  62. .PP
  63. Inorder traversal for an n-ary tree is defined to traverse the left-most 
  64. subtree, visit the node, then traverse all remaining subtrees from left to 
  65. right. Postorder traversal of an n-ary tree is defined to traverse all subtrees 
  66. from left to right, then visit the node. Preorder traversal for an n-ary tree 
  67. is defined to visit the node, then traverse all subtrees from left to right. 
  68. The reverse traversal modes are similar, except that they visit subtrees from 
  69. right to left.
  70. .SH Base Classes
  71.  
  72. .SH Friend Classes
  73. None
  74. .SH Constructors
  75. .TP
  76. \f3N_Tree<Node,Type,nchild> (Node<Type,nchild>& n\f3);\f1
  77. Allocates an n-ary tree object with the root pointer set to 
  78.  n .
  79. .TP
  80. \f3N_Tree<Node,Type,nchild> (Node<Type,nchild>* n\f3);\f1
  81. Allocates an n-ary tree object with the root pointer set to
  82.  n .
  83. .TP
  84. \f3N_Tree<Node,Type,nchild> (const N_Tree<Node,Type,nchild>& nt\f3);\f1
  85. Duplicates the structure of another n-ary tree object 
  86.  nt .
  87. .SH Member Functions
  88. .TP
  89.  void clear ();
  90. Empties the tree and deallocates the memory for all nodes and internal 
  91. structures.
  92. .TP
  93.  inline long count () const;
  94. Returns the number of nodes in the tree structure. Note that this function is 
  95. potentially very expensive, since the tree depth is calculated by traversing 
  96. all nodes in the tree.
  97. .TP
  98.  inline long current_depth ();
  99. Returns the zero-relative depth in the n-ary tree object of the node at the 
  100. current position. If the current position is invalid, this function returns 
  101. zero.
  102. .TP
  103.  inline N_Tree_state& current_position ();
  104. Returns a reference to the state information associated with the current 
  105. position. This function should be used with the 
  106.  Iterator< Type>  
  107. class to save 
  108. and restore the current position, thus facilitating multiple iterators over an 
  109. instance of n-ary tree.
  110. .TP
  111. \f3Boolean find (const Type& value\f3);\f1
  112. Searches for 
  113.  value 
  114. in the tree. If found, this function updates the current 
  115. position and returns
  116.  
  117.  TRUE ; 
  118. otherwise, this function invalidates the current 
  119. position and returns 
  120.  
  121.  FALSE .
  122. .TP
  123. \f3void inorder (\f2Node_Apply_Function fn\f3);\f1
  124. Performs an in-order traversal of the tree structure and applies the function 
  125.  fn 
  126. to each node. Inorder traversal for an n-ary tree is defined to traverse the 
  127. left-most subtree, visit the node, then traverse all remaining subtrees from 
  128. left to right. 
  129.  Node_Apply_Function 
  130. is a function of type 
  131.  Boolean 
  132. (\f2*Function\f1)(\f3const Type& value\f1) where 
  133.  value 
  134. is the value from each node visited 
  135. that is substituted during the traversal.
  136. .TP
  137.  inline Boolean next ();
  138. Advances the current position to the next element if there is one. This 
  139. function returns 
  140.  
  141.  TRUE 
  142. if successful. If the current position is invalid, this 
  143. function sets the current position to the first element and returns 
  144.  
  145.  TRUE .  
  146. If 
  147. the current position is the last element in the tree, this function invalidates 
  148. the current position and returns 
  149.  
  150.  FALSE .
  151. .TP
  152. \f3inline Node<Type,nchild>*\f3& operator[\^] (int \f2index\f3);\f1
  153. Returns a reference to a pointer to the zero-relative indexed subtree. If 
  154.  index 
  155. is negative or out of range, an 
  156.  \f3\f3Error\f1\f1 
  157. exception is raised.
  158. .TP
  159. \f3inline operator Node<Type,nchild>();\f1
  160. Provides an implicit conversion operator from an n-ary tree object to the node 
  161. over which the class is parameterized.
  162. .TP
  163. \f3void postorder (\f2Node_Apply_Function fn\f3);\f1
  164. Performs a post-order traversal of the tree structure and applies the function 
  165.  fn 
  166. to each node. Postorder traversal of an n-ary tree is defined to traverse 
  167. all subtrees from left to right, then visit the node. 
  168.  Node_Apply_Function 
  169. is a 
  170. function of type
  171.   Boolean 
  172. (\f2*Function\f1)(\f3const Type& value\f1) where \f2value\f1 is the 
  173. value from each node visited that is substituted during the traversal.
  174. .TP
  175. \f3void preorder (\f2Node_Apply_Function fn\f3);\f1
  176. Performs a pre-order traversal of the tree structure and applies the function 
  177.  fn 
  178. to each node. Preorder traversal for an n-ary tree is defined to visit the 
  179. node, then traverse all \p
  180. subtrees from left to right.  
  181.  Node_Apply_Function 
  182. is a 
  183. function of type 
  184.  Boolean 
  185. (\f2*Function\f1)(\f3const Type& value\f1) where 
  186.  value 
  187. is the 
  188. value from each node visited that is substituted during the traversal.
  189. .TP
  190.  Boolean prev ();
  191. Moves the current position to the previous element in the tree and returns
  192.  
  193.  TRUE .  
  194. If the current position is invalid, this function sets the current 
  195. position to the last element and returns 
  196.  
  197.  TRUE .  
  198. If the current position is the 
  199. first element in the tree, this function invalidates the current position and 
  200. returns 
  201.  
  202.  FALSE .
  203. .TP
  204.  inline void reset ();
  205. Invalidates the current position for the n-ary tree object.
  206. .TP
  207.  inline Traversal_Type& traversal ();
  208. Returns a reference to the traversal mode. This member function can be used to 
  209. set or get the current traversal mode.
  210. .TP
  211.  Type& value ();
  212. Returns a reference to the value of the node at the current position. If the 
  213. current position is invalid, an 
  214.  \f3\f3Error\f1\f1 
  215. exception is raised.
  216. .SH COPYRIGHT
  217.  
  218. Copyright (C) 1991 Texas Instruments Incorporated.
  219.  
  220. Permission is granted to any individual or institution to use, copy, modify,
  221. and distribute this software, provided that this complete copyright and
  222. permission notice is maintained, intact, in all copies and supporting
  223. documentation.
  224.  
  225. Texas Instruments Incorporated provides this software "as is" without
  226. express or implied warranty.
  227.  
  228.